In the last several years, computer architecture has undergone significant changes, particularly in the area of memory hierarchies, i.e., where a memory system is built of more than one memory technology.
A typical example of such a system is in the use of a cache memory. Generally, cache memory is a small, fast, associative memory located between the central processing unit (CPU) and the main memory. Conceptually to the micromachine, a cache memory looks like nothing other than a very fast main memory. Internally, however, the cache memory works by keeping pieces of main memory (called blocks, always a power of two words in size) in a local very high speed RAM. However, to keep track of these blocks, the cache needs to keep an identifier with each one. These identifiers are called TAGs and are the main memory address of each block. In a set associative cache, the "frame" into which main memory blocks can be placed are distinguished by their lower addresses. Thus, any two blocks can both be in the cache as long as their lower addresses are not the same. If their lower addresses are the same, then the TAG need not have the lower address bits, since each block is identified simply by the frame in which it is being kept.
During a cache access, the cache uses the lower address bits to select a cache frame. The TAG from this frame is compared to the upper address bits to see if they match. If so, then the data in that frame is what is desired. If the TAG does not match with the upper address bits, then a "miss" has occurred. To keep the CPU from knowing that something is wrong, the CPU is frozen. The cache then takes the TAG and the lower address bits and writes its present block back into main memory. It then uses the total address from the CPU to read a new block from main memory. This block is then stored in the cache with the TAG set to the new upper address bits. (See, for example, "Computer Engineering--a DEC View of Hardware System Design", 1978, Chapter 10, pages 263-267, entitled "Cache Memories for PDP-11 Family Computers" by William D. Strecker.)
Also in the prior art, it is customary to use a logical address to physical address translation in order to expand the number of physical memory locations which can be addressed by the CPU. This is generally accomplished by using a portion of the CPU address as a logical address, and then using a dynamic mapping system, typically a map RAM, between the CPU and the cache as an address decoder. With this scheme, the total memory address is not known until after the map RAM access, which is serial in the cache access time. Hence, to speed up cache access, it is conventional to make the map RAM as fast as possible. Unfortunately, however, these faster RAMs are less dense, take up more board space, and are also expensive on a per bit basis.